题解 CF117C Cycle

发表于 | 更新于

题目大意：给定一个竞赛图(有向完全图，从数据保证$map[i][i]=0$，$map[i][j]≠map[j][i]$。可以看出)，找出一个长度为$3$的环。

竞赛图的重要性质：

竞赛图没有自环，没有二元环；若竞赛图存在环，则一定存在三元环。

前半句话浅显易懂，后半句话的意思就是说：竞赛图要么没有环，如果存在一个环大于三元，那么一定存在另一个三元的小环。

简单证明：
假设一个竞赛图存在一个$N$元环(大于三元),环上有连续三点$A,B,C$(存在有向边$AB,BC)$

根据竞赛图的定义，一定存在有向边$CA$或$AC$中的一者。

情况$1:$若存在$CA,$则$A,B,C$构成三元环；

情况$2:$若存在$AC$，不考虑$B$点，剩下的点构成一个$(N-1)$元环。显然，如果一直不存在情况$1$的话，最终也会形成一个三元环。

下面用类似$dfs$的$tanjan$寻找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
using namespace std; 
char s[5005];
int n,low[39393],col,flag,in[39393],dfn[39393],st[39393],w[39393],t[39393],tot,vis[39393],top,num;
bool a[5005][5005];
void Tarjan(int u){
    if (flag)return;
    if (in[u]&&st[top]!=u){
        flag=1;
        while (st[top]!=u)t[++tot]=st[top--];
        t[++tot]=u;
        return;
    }
    if (vis[u])return;
    st[++top]=u;in[u]=vis[u]=1;
    for (int v=1;v<=n;++v)
        if (a[u][v])
            Tarjan(v);
    --top;
    in[u]=0;
}
int main(){
    scanf("%d",&n);
    for (int i=1;i<=n;++i){
           scanf("%s",s+1);
           for (int j=1;j<=n;++j)
               if (s[j]=='1')a[i][j]=1;
    }
    for (int i=1;i<=n;++i)
        if (!vis[i])Tarjan(i);
    if (!flag){puts("-1");return 0;}
    for (int j=3;j<=tot;++j)
        if (a[t[1]][t[j]]){
            printf("%d %d %d\n",t[1],t[j],t[j-1]);
            return 0;
        }//如果枚举到j，说明之前有一条j-1到1的有向边，因为如果有1到j-1的有向边，之前程序就该结束了，不可能循环到j
    printf("%d %d %d\n",t[1],t[tot],t[tot-1]);//单独特判
    return 0;
}